1. Field of the Invention
The present invention generally relates to a processor and an instruction pipeline thereof, and a storage apparatus and a controller thereof, and more particularly, to a method for recovering a global history shift register (GHSR) and a method for recovering a return address stack (RAS) thereof.
2. Description of Related Art
For achieving an improved efficiency, most current processors employ instruction pipeline configurations. In an instruction pipeline configuration, the branch prediction technology often plays a very important role for allowing each stage of the instruction pipeline working in each clock duty cycle, without being idled.
Typically, a high accurate branch predictor is often facilitated by a global history of the branch instruction for prediction. Such a global history is usually saved in a global history shift register (GHSR). The GHSR needs a correct branch direction for updating, and thus providing an accurate prediction. However, a correct branch direction of a branch instruction cannot be determined until an execution stage. If a newly entered branch instruction needs to use the global history for facilitating prediction before the branch direction is determined and before the GHSR is updated, the prediction accuracy will decline. As such, it is proposed to execute a speculative update to the GHSR. Specifically, when a prediction result of a branch instruction is attained, the prediction result is used to update the GHSR. However, such a speculative update requires a recovering mechanism after the branch direction is determined for assuring the correctness of the global history.
According to a conventional technology, a content of an instant GHSR is saved for each branch instruction, and when a prediction of the branch instruction is found incorrect later, a previously saved content will be loaded to the GHSR for concealing the speculatively updated incorrect branch direction.
According to another conventional technology, two GHSRs are employed. One of the two is written after the branch direction is determined, thus having an absolutely correct content, while another one is provided for speculative updating. Normally, the branch prediction uses the GHSR for speculative updating. However, when the predicted branch direction is found incorrect, the absolutely correct content of the GHSR which is written after the branch direction is determined is loaded to the GHSR for speculative updating for concealing the speculatively updated incorrect branch direction.
Further, in designing a current processor, for the purpose of executing branch prediction for call instructions and return instructions, the instruction pipeline employs a return address stack (RAS) specifically regarding this kind of instructions for storing target addresses of the return instructions corresponding to the call instructions. However, the instruction pipeline may be executed with a flush operation. In this case, an instruction which has been fetched in and should be flushed may include one of the types of branch instructions (e.g., a call instruction or a return instruction) which have executed corresponding actions to the RAS. Therefore, flushing the instruction pipeline may cause the content of the RAS to be incorrect, and may further generate an error of a return address provided to the return instruction.
According to a conventional technology, an instant top-of-stack pointer is recorded when each branch instruction enters the instruction pipeline, and when a prediction error occurs, the top-of-stack pointer is set with a previously recorded value.
According to another conventional technology, an address popped out from the RAS is retained, and when a prediction error occurs, the retained address is pushed into the RAS. However, this conventional technology does not distinguish the order of the retained addresses.
However, the clock rates of the processors are developed to be faster and faster, and correspondingly stages of the instruction pipeline are divided finer and finer, and therefore the branch prediction technology is now demanded for dealing with more and more complicated situations. As such, all of the aforementioned conventional technologies have disadvantages. They either require additional hardware components which increase processing cost, or are incapable of completely recovering a status of the instruction pipeline when a complex prediction error occurs.